package algorithms.question.class10;

import common.util.MyUtil;

/**
 * https://leetcode-cn.com/problems/boolean-evaluation-lcci/
 * <p>
 * 给定一个布尔表达式和一个期望的布尔结果 result，布尔表达式由 0 (false)、1 (true)、& (AND)、 | (OR) 和 ^ (XOR) 符号组成。
 * 实现一个函数，算出有几种可使该表达式得出 result 值的括号方法。
 *
 * @author guichang
 * @date 2021/8/7
 */

@SuppressWarnings("all")
public class Code5_布尔运算 {

    public static void main(String[] args) {
        String str = "0&0&0&1^1|0";
        MyUtil.print(countEval(str, 1));
    }

    /**
     * @param str    待计算字符串
     * @param result 0-false 1-true
     */
    public static int countEval(String str, int result) {
        if ((result != 0 && result != 1) || str == null || (str.length() & 1) == 0) {
            return 0;
        }
        int N = str.length();
        Info[][] dp = new Info[N][N];
        Info info = process(str.toCharArray(), 0, N - 1, dp);
        return result == 1 ? info.t : info.f;
    }

    /**
     * 递归返回的对象
     */
    public static class Info {
        int t; // 计算结果为true的方法数
        int f; // 计算结果为false的方法数

        public Info(int t, int f) {
            this.t = t;
            this.f = f;
        }
    }

    /**
     * 递归含义：在str的L-R范围内计算出Info，L-R返回个数为奇数且LR非0即1
     */
    public static Info process(char[] strs, int L, int R, Info[][] dp) {
        if (dp[L][R] != null) {
            return dp[L][R];
        }
        int t = 0;
        int f = 0;
        // L和R相同位置就只有一种情况了
        if (L == R) {
            t = strs[L] == '1' ? 1 : 0;
            f = strs[L] == '0' ? 1 : 0;
        }
        // L和R至少隔3个数，遍历每个逻辑运算符累加上结果
        else {
            for (int i = L + 1; i <= R - 1; i += 2) {
                Info left = process(strs, L, i - 1, dp);
                Info right = process(strs, i + 1, R, dp);
                int lt = left.t;
                int lf = left.f;
                int rt = right.t;
                int rf = right.f;
                switch (strs[i]) {
                    case '&':
                        t += lt * rt; // 两边都必须是true
                        f += lt * rf + lf * rt + lf * rf; // 两边都必须不同时为true
                        break;
                    case '|':
                        t += lt * rt + lt * rf + lf * rt; // 两边都必须不同时为false
                        f += lf * rf; // 两边都必须同时为false
                        break;
                    case '^':
                        t += lt * rf + lf * rt; // 两边都必须不同
                        f += lt * rt + lf * rf; // 两边都必须相同
                        break;
                }
            }
        }
        dp[L][R] = new Info(t, f);
        return dp[L][R];
    }

}